/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/wildcard-matching
   @Language: C++
   @Datetime: 19-03-12 09:50
   */


// Method 1, Time 50ms
class Solution {
public:
	/**
	 * @param s: A string 
	 * @param p: A string includes "?" and "*"
	 * @return: is Match?
	 */
	bool isMatch(string &s, string &p) {
		// write your code here
		int n=s.length(), m=p.length();
		vector<vector<bool> > dp(n+1,vector<bool>(m+1,false));
		dp[0][0]=true;
		for(int i=0; i<m; i++)
			if (p[i]=='*') dp[0][i+1]=dp[0][i];
		for(int i=0; i<n; i++){
			for (int j=0; j<m; j++){
				if (p[j]=='*'){
					dp[i+1][j+1] = dp[i][j] | dp[i][j+1] | dp[i+1][j];
				}
				else if (p[j]=='?'){
					dp[i+1][j+1] = dp[i][j];
				}
				else dp[i+1][j+1] = dp[i][j] & (s[i]==p[j]);
			}
		}
		return dp[n][m];
	}
};

// Method 2, Time 7ms
class Solution {
public:
	/**
	 * @param s: A string 
	 * @param p: A string includes "?" and "*"
	 * @return: is Match?
	 */
	bool isMatch(string &s, string &p) {
		// write your code here
		int i=0, j=0, last=0, star=-1;
		while(i<s.length()){
			if (j<p.length() && (s[i]==p[j] || p[j]=='?')){
				i++;
				j++;
			}
			else if (j<p.length() && p[j]=='*'){
				last=i;     // * as 0 char
				star=j++;
			}
			else if (star!=-1){
				i=++last;   // * as +1 char
				j=star+1;
			}
			else return false;
		}
		for(; j<p.length() && p[j]=='*'; j++);
		return j==p.length();
	}
};


